package com.ryujung.greedy;

class Solution45 {
    /**
     * 思路二：
     * 当前位置可以确定下一步的行动范围，
     * 需要在范围内找到最大的移动距离，然后从当前范围的尾部~最大距离再去寻找在下一步的最大距离，
     * 可以看出当前范围的尾部到新的最大距离，整个是连续的，只是最大距离改变了，最大距离以为着一次行动的结束，增加新的步数
     * 整个过程需要将0~length-1整个遍历一次，
     * 然后根据是否到达本次行动的最大距离，然后增加步数
     */
    public int jump2(int[] nums) {
        int res = 0;
        int end = 0,max = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            max = Math.max(max, i + nums[i]);
            if (i == end) {
                res++;
                end = max;
            }
        }
        return res;
    }

    /**
     * 方式一：
     * <p>
     * 137...
     * 思路：
     * 题目确定可以到达n-1，可以不用考虑无法到达的问题
     * 每次所处的位置，都会给出下次移动的范围start~end，需要在这个范围中找到行动最远的距离，
     * 例如：初始index=0，nums[0] = 3，那么start~end= 1~3
     * 遍历start~end，获取nums[i]+i在这个区间的最大值，
     * 下一次可以行动的范围就变成了 end+1~max(nums[i]+i)这个区间，也就是新的start和end
     * 当最大行动范围达到length-1时，即结束上述步骤，将其中行动的次数返回即可
     */
    public int jump(int[] nums) {
        int res = 0;
        int start = 0, end = 0;
        while (end < nums.length - 1) {
            // 重置max
            int max = 0;
            // 明确本次行动的范围
            for (int i = start; i <= end; i++) {
                // 确定当前行动的最大范围
                max = Math.max(max, i + nums[i]);
            }
            res++;
            // 更新下次行动的范围 end+1~max
            start = end + 1;
            end = max;
        }
        return res;
    }

    public static void main(String[] args) {
        Solution45 s = new Solution45();
        System.out.println("answer:2");
        System.out.println(s.jump(new int[]{2, 3, 1, 1, 4}));
        System.out.println("answer:2");
        System.out.println(s.jump(new int[]{2, 3, 0, 1, 4}));
        System.out.println(s.jump(new int[]{5, 9, 3, 2, 1, 0, 2, 3, 3, 1, 0, 0}));
        System.out.println(s.jump(new int[]{6, 9, 1, 5, 6, 0, 0, 5, 9}));
    }
}